#!/usr/bin/env python
# -*- coding:utf-8 -*-
# @Author  : 1230
# @Email   : xjh_0125@sina.com
# @Time    : 2021/3/26 9:51
# @Software: PyCharm
# @File    : l797_all_path_graph.py

class Solution:
    def __init__(self):
        """
        给一个有 n 个结点的有向无环图，找到所有从 0 到 n-1 的路径并输出（不要求按顺序）
        """
        pass

    def allPathsSourceTarget(self, graph):
        '''
        回溯算法
        :param graph:
        :return:
        '''

        def traverse(graph, s, path):
            nonlocal res
            path.append(s)
            n = len(graph)
            if s == n - 1:
                res.append(path.copy())
                path.pop()
                return
            for v in graph[s]:
                traverse(graph, v, path)
            path.pop()

        res, path = [], []
        traverse(graph, 0, path)
        return res


if __name__ == '__main__':
    s = Solution()
    graph = [[1, 2], [3], [3], []]
    print(s.allPathsSourceTarget(graph))
